Due to its low cost, an Internet Protocol (IP) network is becoming an important social infrastructure that will replace a telephone network. Therefore, the IP network is now required to assure communication quality (QoS: Quality of Service) that has been provided by a conventional telephone network. More specifically, it is demanded, for instance, that the IP network achieve high-speed recovery from a network failure, offer high reliability, and assure low delay time and low drop rate.
For example, a high-speed path switching technology (prior art 1), which is based on MPLS (Multi-Protocol Label Switching), is available as a network failure recovery method (refer to Non-Patent Documents 1 (E. Rosen, A. Viswanathan, R. Callon, “Multiprotocol Label Switching Architecture”, RFC3031, Internet Engineering Task Force, January, 2001) and 2 (E. Rosen, T. Tappan, G. Fedorkow, Y. Rekhter, D. Farinacci, T. Li, A. Conta, “MPLS Label Stack Encoding”, RFC3032, Internet Engineering Task Force, January, 2001) for MPLS and Non-Patent Document 3 (P. Pan, G. Swallow, A. Atlas, “Fast Reroute Extensions to RSVP-TE for LSP Tunnels”, RFC4090, Internet Engineering Task Force, 2004) for the MPLS-based high-speed path switching technology).
First of all, MPLS will be summarized. MPLS is a packet forwarding method in which a router determines the packet forwarding destination in accordance with the value of a label attached to a packet.
The MPLS-based packet forwarding method will now be summarized with reference to FIG. 1.
FIG. 1 illustrates an MPLS network 100. The MPLS network 100 comprises edge routers ER1 (141), ER2 (142), ER3 (143), and ER4 (144), which are positioned at an entry or exit of the network, and core routers CR1 (151), CR2 (152), and CR3 (153), which are positioned within the MPLS network 100. The MPLS network 100 is configured, for instance, with a second layer transfer protocol (e.g., Ethernet (registered trademark)). A case where Ethernet is used as the second layer transfer protocol is used will be described below.
Each edge router accommodates a plurality of networks (networks NA (161), NB (162), NC (163), and ND (164)), which are interconnected via the MPLS network. Each edge router receives a packet from the accommodated networks, capsules the received packet with an MPLS capsule header, and forwards the capsuled packet to the MPLS network 100. For the sake of brevity, FIG. 1 shows only a label in the MPLS capsule header. For example, edge router ER1 receives packet P1 (171) from network NA, capsules packet P1 (171) with the MPLS capsule header, which contains label L11 (111), and forwards the capsuled packet to core router CR1. In this instance, the output port 181, label L11, and other MPLS capsule header elements are determined by using intra-header information such as the third layer transfer protocol (e.g., IP) of packet P1. A case where IP is used as the third layer transfer protocol will be described below.
Core routers CR1 and CR2 uses the MPLS capsule header to determine the output port and a new capsule header for output. If, for instance, core router CR1 receives packet P1, uses the value of label L11, which is attached to packet P1, to search for a label table retained in core router CR1, and determines output port 1020-1, output label L12 (112), and IP 152-1, which is the next forwarding destination IP address (hereinafter referred to as the next hop IP) that is assigned to the interface for port 1020-1 for router CR2 for next forwarding. Core router CR1 replaces label L11, which is attached to packet P1, with label L12. Further, core router CR1 determines a MAC (Media Access Control) address (MAC 152-1) that is assigned to the interface of port 1020-1 for core router CR2 from the next hop IP (IP 152-1), and gives the determined MAC address as the destination MAC address for the Ethernet frame. Subsequently, core router CR1 transmits packet P1 to output port 1020-1. The label attached to a received packet is hereinafter referred to as an input label. The label newly attached by a router at the time of transmission is hereinafter referred to as an output label. Similarly, core router CR2 determines the output port 182, output label L13 (113), and next hop IP (IP 143) for packet P1 to which input label L12 is attached, replaces input label L12 with output label L13, determines the destination MAC address (MAC 143) from the next hop IP (IP 143), gives the determined destination MAC address to the Ethernet frame, and transmits the packet to the output port 182.
When edge router ER3 receives packet P1 to which label L13 is attached, edge router ER3 uses label L13 only or label L13 and the information within the header for the third layer transfer protocol (IP in the present example) for packet P1 to determine the forwarding destination (network NC in FIG. 1), output port 183, and next hop IP, removes the MPLS capsule header, and transmits packet P1 to port 183. Packet P2 is also forwarded in the same manner as described above.
As described above, labels L11, L12, and L13 are used to forward packet P1 through a path between routers ER1 and CR1, a path between routers CR1 and CR2, and a path between routers CR2 and ER3. Labels L21, L22, and L23 are used to forward packet P2 through a path between routers ER2 and CR1, a path between routers CR1 and CR2, and a path between routers CR2 and ER4. These paths are called label switched paths (LSPs). The LSPs are set in accordance with a label distribution protocol or manually set by a network administrator. Available label distribution protocols include Label Distribution Protocol (LDP), Constraint-based Routing Label Distribution Protocol (CR-LDP), and Extensions to Resource Reservation Protocol for LSP Tunnels (RSVP-TE) (refer to Non-Patent Document 4 (L. Andersson, “LDP Specification”, RFC3036, Internet Engineering Task Force, January 2001) for LDP, Non-Patent Document 5 (B. Jamoussi, “Constraint-Based LSP Setup using LDP”, RFC3212, Internet Engineering Task Force, January 2002) for CR-LDP, and Non-Patent Document 6 (D. Awduche, L. Berger, T. Li, V. Srinivasan, G. Swallow, “RSVP-TE: Extensions to RSVP for LSP Tunnels”, RFC3209, Internet Engineering Task Force, December 2001) for RSVP-TE).
Since the LSPs can be explicitly set, MPLS is advantageous in that it can offer paths in compliance with communication quality requirements for each traffic and permit traffic engineering for intra-network path load distribution.
A technology called “Facility Backup”, which is one of the MPLS-based high-speed path switching technologies described in Non-Patent Document 3 (P. Pan, G. Swallow, A. Atlas, “Fast Reroute Extensions to RSVP-TE for LSP Tunnels”, RFC4090, Internet Engineering Task Force, 2004), will now be described with reference to FIGS. 2 and 3.
This high-speed path switching technology sets only one switching LSP for a plurality of LSPs, which are set for the same port, in order to perform switching when the port becomes faulty. The LSP for switching in the event of a fault is hereinafter referred to as a stand-by LSP. The LSP for use under normal conditions is hereinafter referred to as an active LSP. When the high-speed path switching technology is employed, a label stack technology is used. The label stack technology assigns two or more labels in order to minimize the number of label table entries that are used to determine the output label and output port for an end-point router of the stand-by LSP.
FIGS. 2 and 3 illustrate only the MPLS network 100, which is one of the elements shown in FIG. 1. Networks NA, NB, NC, and ND are excluded from FIGS. 2 and 3.
FIG. 2 shows a packet forwarding operation that is performed while port 1020-1 is normal. FIG. 3 shows a packet forwarding operation that is performed while port 1020-1 is faulty (a fault in port 1020-1 is indicated by the letter “X” in FIG. 3).
FIG. 2 assumes that the LSP used to forward packet P1 while port 1020-1 is normal is LSP 1, and that the LSP used to forward packet P2 is LSP 2. The labels used for forwarding are the same as indicated in FIG. 1. The labels used for LSP 1 are label L11 (111), which is for a path between routers ER1 and CR1; label L12 (112), which is for a path between routers CR1 and CR2; and label L13 (113), which is for a path between routers CR2 and ER3. The labels used for LSP 2 are label L21 (121), which is for a path between routers ER2 and CR1; label L22 (122), which is for a path between routers CR1 and CR2; and label L23 (123), which is for a path between routers CR2 and ER4.
In FIG. 3, stand-by LSP 3, which is set for port 1020-1 for LSP 1 and LSP 2, is set for port 1020-2, which is for a path between routers CR1 and CR2, and set for port 184, which is for a path between routers CR3 and CR2. It is assumed that the label for use between routers CR1 and CR3 is label L31 (131), and that the label for use between routers CR3 and CR2 is label L32 (132).
A method for forwarding packet P1 when port 1020-1 is faulty will now be described with reference to FIG. 3. When core router CR1, which is shown in FIG. 3, detects a fault in port 1020-1, applies a change so that output labels L12 and L31 are used for input label L11 within the label table although only one output level (output level L12) has been formerly used. Further, core router CR1 applies another change so that output port 1020-2 is used in place of output port 1020-1. Still another change is also applied to the next hop IP so that IP 153 for router CR3 is used in place of IP 152 for router CR2. Router CR1 receives packet P1, and then determines from input label L11 to use output labels L12 and L31, output port 1020-2, and next hop IP 153. Subsequently, input label L11 is removed from packet P1. The label stack function is then exercised to give the aforementioned two output labels. In this instance, label L31, which is for use with the stand-by LSP, is given to a level higher than that for label L12 (to a position for early data transfer), which is for use with the active LSP 1.
Further, the MAC address (MAC 153) assigned to the interface for port 1020-2 of router CR3 is determined from the next hop IP (IP 153) and given as the destination MAC address for the Ethernet frame. Subsequently, router CR1 transmits packet P1 to port 1020-2. Upon receipt of packet P1, router CR3 uses only label L31 to decide on output port 184, output label L32, and next hop IP 152-2. It should be noted that label L31 is one of the two labels assigned to packet P1 and placed at a high position. Router CR3 replaces only input label L31 with output label L32. It should be noted that input label L31 is one of the input labels assigned to packet P1 and placed at a high position. The MAC address (MAC 152-2) assigned to the interface for port 184 of router CR2 is determined from the next hop IP (IP 152-2) and given as the destination address for the Ethernet frame. Subsequently, router CR3 transmits packet P1 to port 184. Upon receipt of packet P1, which is transmitted from router CR3, router CR2 recognizes from the value of label L32, which is one of the two labels assigned to packet P1 and placed at a high position, that router CR2 is positioned at the end point of stand-by LSP 3, and judges that the output port and output label should be determined by using label L12, which is assigned below label L32.
Subsequently, router CR2 uses label L12 to decide on output port 182, output label L13, and next hop IP 143. Router CR2 removes label L32 from packet P1 and replaces label L12 with output label L13. Further, router CR2 determines the MAC address (MAC 143) assigned to the interface for port 182 of router ER3 from the next hop IP (IP 143), and gives the determined MAC address as the destination address for the Ethernet frame. Later, router CR2 transmits packet P1 to port 182.
The method for forwarding packet P2 is the same as for packet P1. Although label L31, which is one of the two output labels assigned by router CR1 and placed at a high position, is the same as for packet P1, the remaining label for packet P2 is label L22. Further, packet P2 differs from packet P1 in that the output label for router CR2 is label L23. As described above, packet P1, which is forwarded through active LSP 1, and packet P2, which is forwarded through active LSP 2, are similarly forwarded through LSP 3.
In FIG. 3, router CR2, which is positioned at the end point of a stand-by LSP, uses high-level label L32 to recognize that router CR2 is positioned at the end point of stand-by LSP 3, and judges that a label (L12 or L22) assigned below label L32 should be used to determine the output port and output label. In this instance, router CR2 has to conduct a label table search twice depending on the employed label table search method. It means that a considerable amount of processing time is required. A PHP (Penultimate Hop Popping) method is used to avoid this problem. When this method is adopted, a router positioned immediately before the end point of a stand-by LSP is used to remove a label that is assigned to a high level. This method will now be described with reference to FIG. 4.
The label assignment method and packet forwarding method shown in FIG. 4 are virtually the same as described with reference to FIG. 3. However, these two figures differ in the label assignment method that is adopted by router CR3, which positioned immediately before end point router CR2 for stand-by LSP 3. Router CR2 uses label L31, which is assigned to a high position of received packets P1 and P2, to recognize that router CR2 is positioned immediately before the end point of stand-by LSP 3. Labels L12 and L22, which are assigned to a low position of label L31, are the same as the label for forwarding through an active LSP at end point router CR2 for stand-by LSP 3. Therefore, when router CR2 uses this label, router CR2 can determine the same output port and output label as for an active LSP. Consequently, router CR3 removes only label L31, which is assigned to a high position, and transmits a packet to output port 184. Router CR2, which receives the packet, uses only one assigned label (label L12 or L22) to determine the output port and output label. When the PHP method described above is used, a label table search needs to be conducted only once at router CR2, and the required processing time is the same as for a forwarding process that is performed with an active LSP.
When a network is formulated by using the ATM (Asynchronous Transfer Mode) technology instead of the MPLS technology, a technology for making a high-speed switch in the event of a fault in an ATM exchange for data transfer (prior art 2) (refer to Patent Document 1 (Japanese Patent JP-A No. 24220/1996)) is available. Prior art 2 has an active routing table, which store normal path translation header information in the ATM exchange in advance, and a stand-by routing table, which stores stand-by path translation header information. Further, prior art 2 has a memory that stores a faulty port and a virtual path identifier (hereinafter referred to as the VPI) for a faulty virtual path as a bitmap. The ATM exchange processes data in the unit of a 53-byte cell. When a cell arrives, the ATM exchange based on prior art 2 references the memory in which the faulty port and faulty VPI are stored, and checks for an output port fault. If the output port is not faulty, the header information stored in the active routing table is used for cell header information translation. If the output port is faulty, the header information stored in the stand-by routing table is used for cell header information translation. After header information translation, the ATM exchange based on prior art 2 transmits the cell to the next ATM exchange.